1. Field of the Invention
The present invention relates to the field of encoding pictorial imagery for reproduction on display or printing systems, and more particularly, to method and apparatus for digital gray scale halftoning of images.
2. Description Relative to the Prior Art
In the area of digital printing (the term "printing" is used to encompass both printing and displaying throughout), gray level has been achieved in a number of different manners. The representation of the intensity, i.e., the gray level, of a color by binary displays and printers has been the object of a variety of algorithms. Binary displays and printers are capable of making a mark, usually in the form of a dot, of a given, uniform size and a specified resolution in marks per unit lengths, typically dots per inch. It has been common to place the marks according to a variety of geometrical patterns such that a group of marks when seen by the eye gives a rendition of an intermediate color tone between the color of the background (usually white paper stock) and total coverage, or solid density.
Continuous tone images contain an apparent continuum of gray levels. As an approximation to continuous tone images, pictorial imagery has been represented via binary halftone technologies. In order to record or display a halftone image with a scanning system, one cell or super pixel of the recording or display surface consists of a jxk matrix of sub-elements where j and k are positive integers. A halftone image is reproduced by printing the respective sub-elements or leaving them blank, in other words, by suitably distributing the printed marks. Each sub-element, or dot is the same size.
A different method of producing gray levels is provided by gray level printing. In such a method, each pixel has the capability to be rendered in one of several different dot sizes. The dot size for a grey level pixel is represented by a grey level output pixel value which is used to determine an exposure time for recording that pixel by say an LED recording element corresponding to that pixel. The longer the exposure time, the more toner is attracted to that particular pixel. See, for example, U.S. Pat. No. 4,680,645 for a method of rendering gray scale images with variable dot sizes.
In gray scale rendering techniques, the proper dot growth patterns are constructed within a template to optimize and stabilize the electrophotographic process. However, this produces screens of fixed frequencies because of the template or cell characteristic. For a given resolution, finer screens can be produced, but at the expense of rendering levels. The present invention seeks to avoid the shortcoming of the template approach through an error-diffusion technique.
Error-diffusion has been used extensively in certain reproduction methods to produce images with acceptable quality. This technique is very good at reproducing the fine details of images. However, the dots produced by error-diffusion are generally too small to be reproduced sufficiently accurately by most marking devices, in particular, electrophotographic marking devices. This shortcoming causes unstable tone scale variation in the picture. This shortcoming and the "wormy" patterns are characteristic of the images produced by error diffusion.
A method has been described which applies the error diffusion technique to binary halftoning. In this method, described in U.S. Pat. 5,055,942, to Levien, the size of superpixels are varied by varying the number of dots within a variable sized unscreened superpixel. Thus, instead of varying the sizes of the individual dots as in gray scale halftoning, Levien provides for binary halftoning in which either a dot is printed or not, and provides gray scale by varying the number of dots in the plurality of dots. The algorithm Levien uses in his error diffusion technique is based upon this binary halftoning, such that each dot represents either a zero or a one. The limitation to binary values of the individual dots produces a less accurate reproduction than a method allowing multiple bit (and dot sizes) for each dot.